package core.java.test.sieve;

import java.util.BitSet;

/**
 * 描述：使用位集计算2000000以内的所有素数
 *
 * @author liuchuang
 * @date 2021/12/14 14:35
 */
public class Sieve {

    public static void main(String[] args) {
        int range = 2000000;
        long begin = System.currentTimeMillis();

        // range+1的大小保证1~200000的数对应到位集上，弃用0
        BitSet bitSet = new BitSet(range + 1);
        int count = 0;
        int start = 2;
        int index;
        for (index = start; index <= range; index++) {
            bitSet.set(index);
        }
        index = start;
        while (index * index <= range) {
            if (bitSet.get(index)) {
                count++;
                int clearIndex = index * index;
                while (clearIndex < range) {
                    bitSet.clear(clearIndex);
                    clearIndex += index;
                }
            }
            index++;
        }
        while (index < range) {
            if (bitSet.get(index)) {
                count++;
            }
            index++;
        }
        long end = System.currentTimeMillis();
        System.out.println(count+"素数");
        assert count == 148933;
        System.out.println("耗时：" + (end - begin) + "毫秒");
    }

}
